/**
 * 希尔排序
 *
 * @param {number[]} nums
 * @return {number[]}
 */
function shellSort(nums) {
  const length = nums.length;
  if (length < 2) {
    return nums;
  }
  let gap = 1;
  while (gap < length / 3) {
    gap = gap * 3 + 1;
  }
  let index;
  let current;
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < length; i++) {
      index = i - gap;
      current = nums[i];
      while (index >= 0 && nums[index] > current) {
        nums[index + gap] = nums[index];
        index -= gap;
      }
      nums[index + gap] = current;
    }
  }
  return nums;
}

const nums = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(shellSort(nums));
